package org.shj.suanfa

/**
 * 此题要求跟 MinOps中的要求差不多，不同的只是可以选择 +1 或 -1
 * 
 * 解题思路：
 * 根据 MinOps 中的思路，这次我们其实是要找一个数，使得大于它的数减到这个数的次数加上小于它的数加到这个数的次数的值最小
 * 假设 已经按从小到大排列的数组为：  a(0),a(1),a(2),...a(i),...a(n-1), 假设第i位的数为我们要找的数，那么：
 * 大于 a(i) 的数减少到这个数的次数为S1： a(n-1)-a(i) + a(n-2)-a(i) + ... + a(i+1)-a(i) = a(i+1)+...+a(n-1) - (n-i-1)*a(i)
 * 小于 a(i) 的数增加到这个数的次数为S2： a(i)-a(0) + a(i)-a(1) + ... + a(i)-a(i-1)  = i*a(i) - (a(0) +...+a(i-1))
 * 
 * 假设数组的和是Sum(n), 从a(0)到a(i)的和为Si, 那么 
 * S1 = Sum(n) - Si - (n-i-1)*a(i)
 * S2 = (i+1)*a(i)-Si
 * 两者之和 S1 + S2 = Sum(n) - 2*Si + (2*i+2-n)*a(i)
 * 只需要求这个和的最小值就好了。 * 
 * 
 */

object MinOps2 {
  def main(args: Array[String]): Unit = {
    val arr = Array(1, 2, 3)
    var minSum = Int.MaxValue
    val n = arr.length
    var Si = 0
    val sum = arr.sum
    
    for(i <- 0 to n-1){
      Si += arr(i)
      var s = sum - 2*Si + (2*i + 2 - n)*arr(i)
      if(s < minSum){
        minSum = s
      }
    }
    println(minSum)
  }
}